home *** CD-ROM | disk | FTP | other *** search
/ Acorn RISC PD-CD 1 / Acorn RISC PD-CD 1.iso / utilities / _graphics / graphics / _jpeg / c / jdhuff < prev    next >
Encoding:
Text File  |  1991-10-28  |  7.6 KB  |  319 lines
  1. /*
  2.  * jdhuff.c
  3.  *
  4.  * Copyright (C) 1991, Thomas G. Lane.
  5.  * This file is part of the Independent JPEG Group's software.
  6.  * For conditions of distribution and use, see the accompanying README file.
  7.  *
  8.  * This file contains Huffman entropy decoding routines.
  9.  * These routines are invoked via the methods entropy_decode
  10.  * and entropy_decoder_init/term.
  11.  */
  12.  
  13. #include "jinclude.h"
  14.  
  15.  
  16. /* Static variables to avoid passing 'round extra parameters */
  17.  
  18. static decompress_info_ptr dcinfo;
  19.  
  20. static unsigned int get_buffer; /* current bit-extraction buffer */
  21. static int bits_left;           /* # of unused bits in it */
  22.  
  23.  
  24. LOCAL void
  25. fix_huff_tbl (HUFF_TBL * htbl)
  26. /* Compute derived values for a Huffman table */
  27. {
  28.   int p, i, l, lastp, si;
  29.   char huffsize[257];
  30.   UINT16 huffcode[257];
  31.   UINT16 code;
  32.   
  33.   /* Figure 7.3.5.4.2.1: make table of Huffman code length for each symbol */
  34.   /* Note that this is in code-length order. */
  35.  
  36.   p = 0;
  37.   for (l = 1; l <= 16; l++) {
  38.     for (i = 1; i <= htbl->bits[l]; i++)
  39.       huffsize[p++] = l;
  40.   }
  41.   huffsize[p] = 0;
  42.   lastp = p;
  43.   
  44.   /* Figure 7.3.5.4.2.2: generate the codes themselves */
  45.   /* Note that this is in code-length order. */
  46.   
  47.   code = 0;
  48.   si = huffsize[0];
  49.   p = 0;
  50.   while (huffsize[p]) {
  51.     while (huffsize[p] == si) {
  52.       huffcode[p++] = code;
  53.       code++;
  54.     }
  55.     code <<= 1;
  56.     si++;
  57.   }
  58.   
  59.   /* Figure 7.3.5.4.2.3: generate encoding tables */
  60.   /* These are code and size indexed by symbol value */
  61.  
  62.   for (p = 0; p < lastp; p++) {
  63.     htbl->ehufco[htbl->huffval[p]] = huffcode[p];
  64.     htbl->ehufsi[htbl->huffval[p]] = huffsize[p];
  65.   }
  66.   
  67.   /* Figure 13.4.2.3.1: generate decoding tables */
  68.  
  69.   p = 0;
  70.   for (l = 1; l <= 16; l++) {
  71.     if (htbl->bits[l]) {
  72.       htbl->valptr[l] = p;      /* huffval[] index of 1st sym of code len l */
  73.       htbl->mincode[l] = huffcode[p]; /* minimum code of length l */
  74.       p += htbl->bits[l];
  75.       htbl->maxcode[l] = huffcode[p-1]; /* maximum code of length l */
  76.     } else {
  77.       htbl->maxcode[l] = -1;
  78.     }
  79.   }
  80. }
  81.  
  82.  
  83. /* Extract the next N bits from the input stream (N <= 8) */
  84.  
  85. LOCAL int
  86. get_bits (int nbits)
  87. {
  88.   int result;
  89.   
  90.   while (nbits > bits_left) {
  91.     int c = JGETC(dcinfo);
  92.     
  93.     get_buffer = (get_buffer << 8) + c;
  94.     bits_left += 8;
  95.     /* If it's 0xFF, check and discard stuffed zero byte */
  96.     if (c == 0xff) {
  97.       c = JGETC(dcinfo);  /* Byte stuffing */
  98.       if (c != 0)
  99.         ERREXIT1(dcinfo->emethods,
  100.                  "Unexpected marker 0x%02x in compressed data", c);
  101.     }
  102.   }
  103.   
  104.   bits_left -= nbits;
  105.   result = (get_buffer >> bits_left) & ((1 << nbits) - 1);
  106.   return result;
  107. }
  108.  
  109. /* Macro to make things go at some speed! */
  110.  
  111. #define get_bit()       (bits_left ? \
  112.                          ((get_buffer >> (--bits_left)) & 1) : \
  113.                          get_bits(1))
  114.  
  115.  
  116. /* Figure 13.4.2.3.2: extract next coded symbol from input stream */
  117.   
  118. LOCAL int
  119. huff_DECODE (HUFF_TBL * htbl)
  120. {
  121.   int l, p;
  122.   INT32 code;
  123.   
  124.   code = get_bit();
  125.   l = 1;
  126.   while (code > htbl->maxcode[l]) {
  127.     code = (code << 1) + get_bit();
  128.     l++;
  129.   }
  130.   
  131.   p = htbl->valptr[l] + (code - htbl->mincode[l]);
  132.   
  133.   return htbl->huffval[p];
  134. }
  135.  
  136.  
  137. /* Figure 13.4.2.1.1: extend sign bit */
  138.  
  139. #define huff_EXTEND(x, s)       ((x) < (1 << ((s)-1)) ? \
  140.                                  (x) + (-1 << (s)) + 1 : \
  141.                                  (x))
  142.  
  143.  
  144. /* Decode a single block's worth of coefficients */
  145. /* Note that only the difference is returned for the DC coefficient */
  146.  
  147. LOCAL void
  148. decode_one_block (JBLOCK block, HUFF_TBL *dctbl, HUFF_TBL *actbl)
  149. {
  150.   int s, k, r, n;
  151.  
  152.   /* zero out the coefficient block */
  153.  
  154.   MEMZERO((void *) block, SIZEOF(JBLOCK));
  155.   
  156.   /* Section 13.4.2.1: decode the DC coefficient difference */
  157.  
  158.   s = huff_DECODE(dctbl);
  159.   r = get_bits(s);
  160.   block[0] = huff_EXTEND(r, s);
  161.   
  162.   /* Section 13.4.2.2: decode the AC coefficients */
  163.   
  164.   for (k = 1; k < DCTSIZE2; k++) {
  165.     r = huff_DECODE(actbl);
  166.     
  167.     s = r & 15;
  168.     n = r >> 4;
  169.     
  170.     if (s) {
  171.       k = k + n;
  172.       r = get_bits(s);
  173.       block[k] = huff_EXTEND(r, s);
  174.     } else {
  175.       if (n != 15)
  176.         break;
  177.       k += 15;
  178.     }
  179.   }
  180. }
  181.  
  182.  
  183. /*
  184.  * Initialize for a Huffman-compressed scan.
  185.  * This is invoked after reading the SOS marker.
  186.  */
  187.  
  188. METHODDEF void
  189. huff_decoder_init (decompress_info_ptr cinfo)
  190. {
  191.   short ci;
  192.   jpeg_component_info * compptr;
  193.  
  194.   /* Initialize static variables */
  195.   dcinfo = cinfo;
  196.   bits_left = 0;
  197.  
  198.   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
  199.     compptr = cinfo->cur_comp_info[ci];
  200.     /* Make sure requested tables are present */
  201.     if (cinfo->dc_huff_tbl_ptrs[compptr->dc_tbl_no] == NULL ||
  202.         cinfo->ac_huff_tbl_ptrs[compptr->ac_tbl_no] == NULL)
  203.       ERREXIT(cinfo->emethods, "Use of undefined Huffman table");
  204.     /* Compute derived values for Huffman tables */
  205.     /* We may do this more than once for same table, but it's not a big deal */
  206.     fix_huff_tbl(cinfo->dc_huff_tbl_ptrs[compptr->dc_tbl_no]);
  207.     fix_huff_tbl(cinfo->ac_huff_tbl_ptrs[compptr->ac_tbl_no]);
  208.     /* Initialize DC predictions to 0 */
  209.     cinfo->last_dc_val[ci] = 0;
  210.   }
  211.  
  212.   /* Initialize restart stuff */
  213.   cinfo->restarts_to_go = cinfo->restart_interval;
  214.   cinfo->next_restart_num = 0;
  215. }
  216.  
  217.  
  218. /*
  219.  * Check for a restart marker & resynchronize decoder.
  220.  */
  221.  
  222. LOCAL void
  223. process_restart (decompress_info_ptr cinfo)
  224. {
  225.   int c, nbytes;
  226.   short ci;
  227.  
  228.   /* Throw away any partial unread byte */
  229.   bits_left = 0;
  230.  
  231.   /* Scan for next JPEG marker */
  232.   nbytes = 0;
  233.   do {
  234.     do {                        /* skip any non-FF bytes */
  235.       nbytes++;
  236.       c = JGETC(cinfo);
  237.     } while (c != 0xFF);
  238.     do {                        /* skip any duplicate FFs */
  239.       nbytes++;
  240.       c = JGETC(cinfo);
  241.     } while (c == 0xFF);
  242.   } while (c == 0);             /* repeat if it was a stuffed FF/00 */
  243.  
  244.   if (c != (RST0 + cinfo->next_restart_num))
  245.     ERREXIT2(cinfo->emethods, "Found 0x%02x marker instead of RST%d",
  246.              c, cinfo->next_restart_num);
  247.  
  248.   if (nbytes != 2)
  249.     TRACEMS2(cinfo->emethods, 1, "Skipped %d bytes before RST%d",
  250.              nbytes-2, cinfo->next_restart_num);
  251.   else
  252.     TRACEMS1(cinfo->emethods, 2, "RST%d", cinfo->next_restart_num);
  253.  
  254.   /* Re-initialize DC predictions to 0 */
  255.   for (ci = 0; ci < cinfo->comps_in_scan; ci++)
  256.     cinfo->last_dc_val[ci] = 0;
  257.  
  258.   /* Update restart state */
  259.   cinfo->restarts_to_go = cinfo->restart_interval;
  260.   cinfo->next_restart_num++;
  261.   cinfo->next_restart_num &= 7;
  262. }
  263.  
  264.  
  265. /*
  266.  * Decode and return one MCU's worth of Huffman-compressed coefficients.
  267.  */
  268.  
  269. METHODDEF void
  270. huff_decode (decompress_info_ptr cinfo, JBLOCK *MCU_data)
  271. {
  272.   short blkn, ci;
  273.   jpeg_component_info * compptr;
  274.  
  275.   /* Account for restart interval, process restart marker if needed */
  276.   if (cinfo->restart_interval) {
  277.     if (cinfo->restarts_to_go == 0)
  278.       process_restart(cinfo);
  279.     cinfo->restarts_to_go--;
  280.   }
  281.  
  282.   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
  283.     ci = cinfo->MCU_membership[blkn];
  284.     compptr = cinfo->cur_comp_info[ci];
  285.     decode_one_block(MCU_data[blkn],
  286.                      cinfo->dc_huff_tbl_ptrs[compptr->dc_tbl_no],
  287.                      cinfo->ac_huff_tbl_ptrs[compptr->ac_tbl_no]);
  288.     /* Convert DC difference to actual value, update last_dc_val */
  289.     MCU_data[blkn][0] += cinfo->last_dc_val[ci];
  290.     cinfo->last_dc_val[ci] = MCU_data[blkn][0];
  291.   }
  292. }
  293.  
  294.  
  295. /*
  296.  * Finish up at the end of a Huffman-compressed scan.
  297.  */
  298.  
  299. METHODDEF void
  300. huff_decoder_term (decompress_info_ptr cinfo)
  301. {
  302.   /* No work needed */
  303. }
  304.  
  305.  
  306. /*
  307.  * The method selection routine for Huffman entropy decoding.
  308.  */
  309.  
  310. GLOBAL void
  311. jseldhuffman (decompress_info_ptr cinfo)
  312. {
  313.   if (! cinfo->arith_code) {
  314.     cinfo->methods->entropy_decoder_init = huff_decoder_init;
  315.     cinfo->methods->entropy_decode = huff_decode;
  316.     cinfo->methods->entropy_decoder_term = huff_decoder_term;
  317.   }
  318. }
  319.